package com.practice.niuke.new_direct_basics.class07;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 给定一个字符串类型的数组strs， 找到一种拼接方式， 使得把所有字符串拼起来之后形成的字符串具有最小的字典序。
 *
 * 解法：
 * （0）字符串str1，字符串str2
 * （1）贪心策略：若 (str1拼接str2后的字典序) <= (str2拼接str1后的字典序)，则 拼接时 str1在前，否则 str2在前
 */
public class Code02_LowestLexicography {

    /**
     * 比较器：
     * 以 str1拼接str2之后的字典序 和 str2拼接str1之后的字典序 进行比较，
     * 若 (str1拼接str2之后的字典序) <= (str2拼接str1之后的字典序)，
     * 则 在字符串拼接时 str1排在前面，否则 str2排在前面。
     */
    public static class MyComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            return (a + b).compareTo(b + a);
        }
    }

    /**
     * 把所有字符串拼起来之后形成的字符串具有最小的字典序
     *
     * @param strs 字符串数组
     * @return String
     */
    public static String lowestString(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        Arrays.sort(strs, new MyComparator());
        String res = "";
        for (int i = 0; i < strs.length; i++) {
            res += strs[i];
        }
        return res;
    }

    public static void main(String[] args) {
        String[] strs1 = {"jibw", "ji", "jp", "bw", "jibw"};
        System.out.println(lowestString(strs1));

        String[] strs2 = {"ba", "b"};
        System.out.println(lowestString(strs2));

    }

}
